package String;//给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
//
// 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [10,2]
//输出："210" 
//
// 示例 2： 
//
// 
//输入：nums = [3,30,34,5,9]
//输出："9534330"
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出："1"
// 
//
// 示例 4： 
//
// 
//输入：nums = [10]
//输出："10"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 100 
// 0 <= nums[i] <= 10⁹ 
// 
// Related Topics 贪心 字符串 排序 👍 797 👎 0


import java.util.Arrays;
import java.util.Comparator;

//leetcode submit region begin(Prohibit modification and deletion)
class largestNumber {
    public String largestNumber(int[] nums) {
        int len = nums.length;
        //将全是0的情况特殊处理
        boolean flag = true;
        for(int i:nums){
            if(i!=0){
                flag = false;
            }
        }
        if(flag){
            return "0";
        }

        //排序，10,2 按字符串排序之后，发现 210 》102
        String[] strs = new String[len];
        //将数字转换为字符串保存
        for(int i=0;i<len;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, len-1);
        StringBuilder sb = new StringBuilder();
        for(String str:strs){
            sb.append(str);
        }

        return sb.toString();

    }

    //自定义快速排序 因为是求最大，所以按照逆序排列
    private void quickSort(String[] strs, int start, int end){
        if(start<end){
            String privot = strs[start];
            int i = start;
            int j = end;
            while(i<j){
//                compareTo(a1,a2)返回为正数表示a1>a2, 返回为负数表示a1<a2, 返回为0表示a1==a2。
                while(i<j && (strs[j] + privot).compareTo(privot+strs[j]) < 0){
                    j--;
                }
                if(i<j){
                    strs[i++] = strs[j];
                }
                while(i<j && (strs[i] + privot).compareTo(privot+strs[i]) > 0){
                    i++;
                }
                if(i<j){
                    strs[j--] = strs[i];
                }

            }
            strs[i] = privot;
            quickSort(strs, start, i-1);
            quickSort(strs, i+1, end);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
